package _18_剑指OfferII;

public class _117_剑指OfferII相似的字符串 {

    int[] parent;

    // 使用并查集
    public int numSimilarGroups(String[] strs) {
        int len = strs.length;
        int subLen = strs[0].length();
        parent = new int[len];
        // 初始化并查集数据
        for (int i = 0; i < len; ++i) {
            parent[i] = i;
        }

        for (int i = 0; i < len; ++i) {
            for (int j = i + 1; j < len; ++j) {
                int parentI = find(parent[i]);
                int parentJ = find(parent[j]);
                // 属于同一个集合
                if (parentI == parentJ) continue;
                if (check(strs[i], strs[j], subLen)) {
                    // 合并并查集, 右向左和并
                    parent[parentJ] = parentI;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < len; ++i) {
            if (parent[i] == i) ans++;
        }
        return ans;
    }

    private int find(int ele) {
        return parent[ele] == ele? ele: find(parent[ele]);
    }

    private boolean check(String str1, String str2, int len) {
        int diff1 = -1;
        int diff2 = -1;
        for (int i = 0; i < len; ++i) {
            if (str1.charAt(i) == str2.charAt(i)) continue;
            if (diff1 == -1) diff1 = i;
            else if (diff2 == -1) diff2 = i;
            else return false;
        }

        return (diff1 == -1 && diff2 == -1) || (diff2 != -1 &&  str1.charAt(diff1) == str2.charAt(diff2));
    }


}
